package structures.trees;

import java.util.Vector;

/**
 * Implements a Binary Search Tree
 */
public class BinarySearchTree implements IBinaryTree {
    
    // The root of the tree
    private TreeNode root;
    
    /**
     * Constructor of the Binary Search Tree
     */
    public BinarySearchTree() {
        this.root = null;
    }
    
    /**
     * Adds a value to the Binary Search Tree
     * @param obj Value to add to the tree
     */
    public void insert(ITreeValue obj) {
        if(this.root == null) {
            this.root = new TreeNode(obj);
        } else {
            TreeNode node = this.root;
            
            while(node != null) {
                if(obj.compareTo(node.getValue()) <= 0) {
                    if(node.getLeft() == null) {
                        node.setLeft(new TreeNode(obj,node));
                        node = null;
                    } else
                        node = node.getLeft();
                } else {
                    if(node.getRight() == null) {
                        node.setRight(new TreeNode(obj,node));
                        node = null;
                    } else
                        node = node.getRight();
                }
            }
        }
    }
    
    /**
     * Removes a value from the Binary Search Tree (the first found)
     * @param obj Value to remove from the tree
     */
    public void remove(ITreeValue obj) {
        TreeNode node = depthFirstSearch(obj);
        if(node != null) {
            
            if(node.getParent().getLeft().equals(node))
                node.getParent().setLeft(null);
            else
                node.getParent().setRight(null);
            
            Vector <TreeNode> rest = traversePreOrderAux(node, new Vector <TreeNode> ());
            rest.remove(0);
            for(int x = 0; x < rest.size(); x++)
                insert(rest.get(x).getValue());
        }
    }
    
    /**
     * Prints the values in a list of tree nodes
     * @param list List of tree nodes from where to print the values
     */
    private void printList(Vector <TreeNode> list) {
        for(int x = 0; x < list.size(); x++)
            list.get(x).getValue().print();
    }
    
    /**
     * Returns a list with the result of a pre-order traversal
     * @return List of the tree's nodes in pre-order
     */
    public Vector<TreeNode> traversePreOrder() {
        Vector<TreeNode> list = new Vector<TreeNode> ();
        return traversePreOrderAux(this.root,list);
    }
    
    /**
     * Returns a list with the result of a pre-order traversal from the given node
     * @param node Node from where to continue the pre-order traversal
     * @param list list with the result of a pre-order traversal from the given node, from the previous iteration
     * @return List of the tree's nodes in pre-order
     */
    private Vector<TreeNode> traversePreOrderAux(TreeNode node,Vector<TreeNode> list) {
        if(node != null) {
            list.add(node);
            traversePreOrderAux(node.getLeft(),list);
            traversePreOrderAux(node.getRight(),list);
        }
        
        return list;
    }
    
    /**
     * Returns a list with the result of a post-order traversal
     * @return List of the tree's nodes in post-order
     */
    public Vector<TreeNode> traversePostOrder() {
        Vector<TreeNode> list = new Vector<TreeNode> ();
        return traversePostOrderAux(this.root,list);
    }
    
    /**
     * Returns a list with the result of a post-order traversal from the given node
     * @param node Node from where to continue the post-order traversal
     * @param list list with the result of a post-order traversal from the given node, from the previous iteration
     * @return List of the tree's nodes in post-order
     */
    private Vector<TreeNode> traversePostOrderAux(TreeNode node,Vector<TreeNode> list) {
        if(node != null) {
            traversePostOrderAux(node.getLeft(),list);
            traversePostOrderAux(node.getRight(),list);
            list.add(node);
        }
        
        return list;
    }
    
    /**
     * Returns a list with the result of a in-order traversal
     * @return List of the tree's nodes in in-order
     */
    public Vector<TreeNode> traverseInOrder() {
        Vector<TreeNode> list = new Vector<TreeNode> ();
        return traverseInOrderAux(this.root,list);
    }
    
    
    /**
     * Returns a list with the result of a in-order traversal from the given node
     * @param node Node from where to continue the in-order traversal
     * @param list list with the result of a in-order traversal from the given node, from the previous iteration
     * @return List of the tree's nodes in in-order
     */
    private Vector<TreeNode> traverseInOrderAux(TreeNode node,Vector<TreeNode> list) {
        if(node != null) {
            traverseInOrderAux(node.getLeft(),list);
            list.add(node);
            traverseInOrderAux(node.getRight(),list);
            
        }
        
        return list;
    }
    
    /**
     * Retrieves the tree node with the requested value by performing a depth first search (the first found)
     * @param value Value to search for
     * @return The tree node with the requested value, null if not found
     */
    public TreeNode depthFirstSearch(ITreeValue value) {
        return depthFirstSearchAux(this.root,value);
    }
    
    /**
     * Retrieves the tree node with the requested value by performing a depth first search
     * @param node Node from where to crawl from
     * @param value Value to search for
     * @return The tree node with the requested value, null if not found
     */
    public TreeNode depthFirstSearchAux(TreeNode node, ITreeValue value) {
        if(node != null) {
            
            if(node.getValue().compareTo(value) == 0)
                return node;
            
            TreeNode temp;
            
            temp = depthFirstSearchAux(node.getLeft(),value);
            
            if(temp != null)
                return temp;
            
            temp = depthFirstSearchAux(node.getRight(),value);
            
            if(temp != null)
                return temp;
        }
        
        return null;
    }
    
    /**
     * Retrieves the tree node with the requested value by performing a breadth first search (the first found)
     * @param value Value to search for
     * @return The tree node with the requested value, null if not found
     */
    public TreeNode breadthFirstSearch(ITreeValue value) {
        if(this.root != null) {
            Vector <TreeNode> nodes = new Vector <TreeNode> ();
            nodes.add(this.root);
            while(nodes.size() > 0) {
                if(nodes.get(0).getValue().compareTo(value) == 0)
                    return nodes.get(0);
                if(nodes.get(0).getLeft() != null)
                    nodes.add(nodes.get(0).getLeft());
                if(nodes.get(0).getRight() != null)
                    nodes.add(nodes.get(0).getRight());
                nodes.remove(0);
            }
        }
        return null;
    }
    
    /**
     * Returns the tree's balance factor
     * @return The tree's balance factor
     */
    public int balanceFactor() {
        return rightBalanceFactor() - leftBalanceFactor();
    }
    
    /**
     * Returns the balance factor of the left subtree
     * @return The left subtree's balance factor
     */
    private int leftBalanceFactor() {
        int maxlevel = 0;
        if(this.root.getLeft() != null)
            maxlevel = balanceFactorAux(this.root.getLeft(),maxlevel);
        return maxlevel;
    }
    
    /**
     * Returns the balance factor of the right subtree
     * @return The right subtree's balance factor
     */
    private int rightBalanceFactor() {
        int maxlevel = 0;
        if(this.root.getRight() != null)
            maxlevel = balanceFactorAux(this.root.getRight(),maxlevel);
        return maxlevel;
    }
    
    /**
     * Crawls the tree until the maximum level is found
     * @param node Node from where to crawl
     * @param max Maximum level found until now
     * @return Returns the maximum level found
     */
    private int balanceFactorAux(TreeNode node, int max) {
        if(node != null) {
            if(node.getLevel() > max)
                max = node.getLevel();
            int temp;
            temp = balanceFactorAux(node.getLeft(), max);
            if(temp > max)
                max = temp;
            temp = balanceFactorAux(node.getRight(), max);
            if(temp > max)
                max = temp;
        }
        
        return max;
    }
    
    public static void main(String [] args) {
        BinarySearchTree tree = new BinarySearchTree();
        
        // TEST ADDITION
        
        tree.insert(new TreeValueInteger(4));
        tree.insert(new TreeValueInteger(23));
        tree.insert(new TreeValueInteger(1));
        tree.insert(new TreeValueInteger(2));
        tree.insert(new TreeValueInteger(0));
        tree.insert(new TreeValueInteger(5));
        tree.insert(new TreeValueInteger(6));
        tree.insert(new TreeValueInteger(-2));
        tree.insert(new TreeValueInteger(-3));
        tree.insert(new TreeValueInteger(-4));
        tree.insert(new TreeValueInteger(-5));
        tree.insert(new TreeValueInteger(-6));
        
        // TEST PRINTING
        System.out.print("Pre-order: ");
        tree.printList(tree.traversePreOrder());
        System.out.println("");
        System.out.print("Post-order: ");
        tree.printList(tree.traversePostOrder());
        System.out.println("");
        System.out.print("In-order: ");
        tree.printList(tree.traverseInOrder());
        System.out.println("");
        
        // TEST DEPTH FIRST SEARCH
        System.out.print("DFS Find 5: ");
        TreeNode result;
        result = tree.depthFirstSearch(new TreeValueInteger(5));
        if(result != null)
            result.getValue().print();
        else
            System.out.print("not found");
        System.out.println("");
        System.out.print("DFS Find 25: ");
        result = tree.depthFirstSearch(new TreeValueInteger(25));
        if(result != null)
            result.getValue().print();
        else
            System.out.print("not found");
        System.out.println("");
        
        // TEST BREADTH FIRST SEARCH
        System.out.print("BFS Find 5: ");
        result = tree.breadthFirstSearch(new TreeValueInteger(5));
        if(result != null)
            result.getValue().print();
        else
            System.out.print("not found");
        System.out.println("");
        System.out.print("BFS Find 25: ");
        result = tree.breadthFirstSearch(new TreeValueInteger(25));
        if(result != null)
            result.getValue().print();
        else
            System.out.print("not found");
        System.out.println("");
        
        // Balance testing
        System.out.println("Left balance factor: " + tree.leftBalanceFactor());
        System.out.println("Right balance factor: " + tree.rightBalanceFactor());
        System.out.println("Balance factor: " + tree.balanceFactor());
    }
    
    public void printPreOrder() {
    }
}
